import math
class Solution:
    def reorganizeString(self, S: str) -> str:
        mapper={}
        maxval=1
        for i in S:
            try:
                mapper[i]+=1
                if mapper[i]>=maxval:
                    maxval=mapper[i]
            except KeyError:
                mapper[i]=1
        print(mapper)
        if maxval>(len(S)+1)//2:
            return ""
        result=""
        key=sorted(mapper.keys(),key=lambda x:mapper[x],reverse=True)
        #print(key)
        index=1
        cands=key[:1]
        i=0
        while index<len(key):
            cands.append(key[index])
            index+=1
            while mapper[cands[i]]>0:
                result+=cands[i]
                mapper[cands[i]]-=1
                i=(i+1)%2
            cands.pop(i)
            if i==0:
                i=1
        if mapper[cands[0]]!=0:
            offset=0
            for i in range(mapper[cands[0]]):
                result=result[:i+offset]+cands[0]+result[i+offset:]
                offset+=1
        return result

s=Solution()
s.reorganizeString("tndsewnllhrtwsvxenkscbivijfqnysamckzoyfnapuotmdexzkkrpmppttficzerdndssuveompqkemtbwbodrhwsfpbmkafpwyedpcowruntvymxtyyejqtajkcjakghtdwmuygecjncxzcxezgecrxonnszmqmecgvqqkdagvaaucewelchsmebikscciegzoiamovdojrmmwgbxeygibxxltemfgpogjkhobmhwquizuwvhfaiavsxhiknysdghcawcrphaykyashchyomklvghkyabxatmrkmrfsppfhgrwywtlxebgzmevefcqquvhvgounldxkdzndwybxhtycmlybhaaqvodntsvfhwcuhvuccwcsxelafyzushjhfyklvghpfvknprfouevsxmcuhiiiewcluehpmzrjzffnrptwbuhnyahrbzqvirvmffbxvrmynfcnupnukayjghpusewdwrbkhvjnveuiionefmnfxao")


'''
执行用时：
40 ms
, 在所有 Python3 提交中击败了
76.84%
的用户
内存消耗：
13.6 MB
, 在所有 Python3 提交中击败了
25.98%
的用户
'''